const BASES: [u64; 7] = [2, 325, 9375, 28178, 450775, 9780504, 1795265022];

fn mod_pow(mut x: u64, mut n: u64, m: u64) -> u64 {
    let mut ret = 1;
    while n > 0 {
        if n & 1 == 1 {
            ret = ((ret as u128) * (x as u128) % (m as u128) ) as u64;
        }
        x = ((x as u128) * (x as u128) % (m as u128) ) as u64;
        n >>= 1;
    }
    ret
}

pub fn miller_rabin(n: u64) -> bool {
    if n < 3 || n % 2 == 0 {
        return n == 2;
    }
    if n % 3 == 0 {
        return n == 3;
    }
    let mut u = n - 1;
    let mut t = 0;
    while u % 2 == 0 {
        t += 1;
        u /= 2;
    }
    for mut a in BASES.iter().cloned() {
        a = a % n;
        if a == 0 || a == 1 || a == n - 1 {
            continue;
        }
        let mut v = mod_pow(a, u, n);
        if v == 1 {
            continue;
        }
        let mut s = 0;
        while s < t {
            if v == n - 1 {
                break;
            }
            v = ((v as u128) * (v as u128) % (n as u128) ) as u64;
            s += 1;
        }
        if s == t {
            return false;
        }
    }
    true
}

pub fn min_edge_prime_num(number: u32) -> String {
    // 设起点数字 1 为第 0 层, 向外依次为第1,2,3...层
    // 则四个对角线的数分别是 (2n+1)^2-m(n+1) for m in [0,1,2,3]
    let mut cur_cycle: u64 = 0;
    let mut cur_total_primes = 0;
    loop {
        cur_cycle += 1;
        for m in 1..4 {
            let num = (2*cur_cycle+1)*(2*cur_cycle+1) - m*2*cur_cycle;
            // 使用 Miller-Rabin 素性测试，判断对角线上的数是否为素数
            if miller_rabin(num) {
                cur_total_primes += 1;
            }
        }
        if (cur_total_primes as f32 / (4*cur_cycle+1) as f32) * 100.0 < number as f32 {
            break;
        }
    }
    vec![2*cur_cycle+1, cur_total_primes].iter().map(|x| x.to_string()).collect::<Vec<String>>().join(",")
}
